#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <cmath>
#include <sstream>
#include <cstring>


void _err_exp()
{
    std::cerr << "错误：无效的表达式" << std::endl;
    std::exit(-1);
}

void _err_Parentheses()
{
    std::cerr << "错误：括号不匹配" << std::endl;
    std::exit(-1);
}

void _err_FirstCharacter()
{
    std::cerr << "错误：第一个有效字符不能为操作符" << std::endl;
    std::exit(-1);
}

void _err_AfterOperator_LastCharacter()
{
    std::cerr << "错误：操作符后面不能为空" << std::endl;
    std::exit(-1);
}

void _err_AfterOperator_InvalidCharacter()
{
    std::cerr << "错误：操作符后面只能接左括号或者数字" << std::endl;
    std::exit(-1);
}

void _err_AfterPoint()
{
    std::cerr << "错误：小数点后面不能为非数字字符" << std::endl;
    std::exit(-1);
}

void _err_BeforePoint_Point()
{
    std::cerr << "错误：小数点在数字串中重复出现" << std::endl;
    std::exit(-1);
}

void _err_BeforePoint_Number()
{
    std::cerr << "错误：小数点前面没有数字" << std::endl;
    std::exit(-1);
}

void _err_DivideZero()
{
    std::cerr << "错误：除数为0" << std::endl;
    std::exit(-1);
}

void _err_FirstCharacter_Parentheses()
{
    std::cerr << "错误：括号内第一个有效字符不能为操作符" << std::endl;
    std::exit(-1);
}

void _err_InvalidCharacter()
{
    std::cerr << "错误：非法字符" << std::endl;
    std::exit(-1);
}

std::queue<char> Infix2Postfix( const char* &character )
{
    std::stack<char> op;
    std::queue<char> expression;
    bool point = false; // 标记是否在数字串中读过'.'
    bool numStart = false; // 标记数字串是否开始
    int j=0;

    if ( character[j] == '+' || character[j] == '*' || character[j]== '/' || character[j]=='^' )
        _err_FirstCharacter();
    if ( character[j] == '-' )
    {
        if ( character[j+1]>='0' && character[j+1]<='9' )
        {
            expression.push(' ');
            expression.push(character[j]);
            numStart = true;
            point = false;
            j++;
        }
        else 
            _err_exp();
    }


    for ( int i=j; character[i]!='\000'; i++ ) 
    {
        char c = character[i];
        char c_next = character[i+1];
        if ( c >= '0' && c <= '9' )
        {
            if ( !numStart )
            {
                expression.push(' ');
                expression.push(c);
                numStart = true;
                point = false;
                if ( c_next!='.' && (c_next<'0' || c_next>'9') )
                {
                    expression.push(' ');
                    numStart = false;
                }
            }
            else if ( c_next!='.' && (c_next<'0' || c_next>'9') )
            {
                expression.push(c);
                expression.push(' ');
                numStart = false;
            }
            else 
                expression.push(c);
            
        }
        else if ( c == '.' )
        {
            if ( c_next<'0' || c_next>'9' )
                _err_AfterPoint();
            if ( !numStart )
                _err_BeforePoint_Number();
            else if ( point )
                _err_BeforePoint_Point();
            else
            {
                expression.push(c);
                point = true;
            }
        }
        else if ( c == ')' )
        {
            if (op.empty())
                _err_Parentheses();
            while(!op.empty() && op.top()!='(')
            {
                expression.push(op.top());
                op.pop();
            }
            if (op.empty())
                _err_Parentheses();
            op.pop();
            continue;
        }
        else if ( c == '+' || c == '-')
        {
            if ( c =='-' && character[i-1]=='(' && c_next>='0' && c_next<='9' )  //此时认为‘-’是数字串的一部分，所以不会放入操作符栈中
            {
                expression.push(' ');
                expression.push(c);
                numStart = true;
                point = false;
                continue;
            }
            if ( c_next=='\000' )
                _err_AfterOperator_LastCharacter();
            else if ( c_next!='(' && (c_next<'0' || c_next>'9') )
                _err_AfterOperator_InvalidCharacter();
            if (!op.empty())
            {
                while ( !op.empty() && op.top() != '(' )
                {
                    expression.push(op.top());
                    op.pop();
                }
            }
            op.push(c);
        }
        else if ( c == '*' || c == '/' )
        {
            if ( c_next=='\000' )
                _err_AfterOperator_LastCharacter();
            else if ( c_next!='(' && (c_next<'0' || c_next>'9') )
                _err_AfterOperator_InvalidCharacter();
            if( !op.empty() )
            {
                while ( !op.empty() && (op.top() == '*' || op.top() == '/') )
                {
                    expression.push(op.top());
                    op.pop();
                }
            }
            op.push(c);
        }
        else if ( c == '^' )
        {
            if ( c_next=='\000' )
                _err_AfterOperator_LastCharacter();
            else if ( c_next!='(' && (c_next<'0' || c_next>'9') )
                _err_AfterOperator_InvalidCharacter();
            if( !op.empty() )
            {
                while ( !op.empty() && (op.top() == '*' || op.top() == '/' || op.top() == '^') )
                {
                    expression.push(op.top());
                    op.pop();
                }
            }
            op.push(c);
        }
        else if ( c == '(' )
        {
            if ( c_next=='\000' )
                _err_AfterOperator_LastCharacter();
            if ( c_next == '+' || c_next == '*' || c_next== '/' || c_next=='^' )
                _err_FirstCharacter_Parentheses();
            if (c_next == '-')
            {
                char c_next2 = character[i+2];
                if ( c_next2 == '\000' )
                    _err_AfterOperator_LastCharacter();
                else if ( c_next2>='0' && c_next2<='9' )
                {
                    op.push(c);
                    continue;
                }
                else if ( c_next2 == '+' || c_next2 == '-' || c_next2 == '*' || c_next2== '/' || c_next2=='^' )
                    _err_FirstCharacter_Parentheses();
            }
            else
                op.push(c);
        }
        else 
            _err_InvalidCharacter();
    }
    while( !op.empty() )
    {
        if ( op.top()=='(' )
            _err_Parentheses();
        expression.push(op.top());
        op.pop();
    }
    return expression;
}

double CalPostfix( std::queue<char> &q )
{
    std::queue<char> c = q;
    std::stack<std::string> cal;
    std::string num;
    while ( !c.empty() )
    {
        if ( c.front()==' ' )
        {
            c.pop();
            continue;
        }   
        if ( c.front()>='0' && c.front()<='9' )
        {
            num.push_back(c.front());
            c.pop();
            if ( c.front()== ' ') 
            {
                cal.push(num);
                num.clear();
            }
        }
        else if( c.front() == '.' )
        {
            num.push_back(c.front());
            c.pop();
        }
        else if ( c.front() == '-' )
        {
            char division = c.front();
            c.pop();
            if ( c.front() >= '0' && c.front() <= '9' )
                num.push_back(division);
            else
            {
                double num1 = std::stod(cal.top());
                cal.pop();
                double num2 = std::stod(cal.top());
                cal.pop();
                std::ostringstream ss;
                ss << (num2 - num1);
                num = ss.str();
                cal.push(num);
                num.clear();
            }
        }
        else if ( c.front() == '+' || c.front() == '*' || c.front() == '/' || c.front() == '^' )
        {
            double num1 = std::stod(cal.top());
            cal.pop();
            double num2 = std::stod(cal.top());
            cal.pop();
            if ( c.front() == '+' )
            {
                std::ostringstream ss;
                ss << (num2 + num1);
                num = ss.str();
                cal.push(num);
                num.clear();
                c.pop();
            }
            else if ( c.front() == '-' )
            {
                std::ostringstream ss;
                ss << (num2 - num1);
                num = ss.str();
                cal.push(num);
                num.clear();
                c.pop();
            }
            else if ( c.front() == '*' )
            {
                std::ostringstream ss;
                ss << (num2 * num1);
                num = ss.str();
                cal.push(num);
                num.clear();
                c.pop();
            }
            else if ( c.front() == '/' )
            {
                std::ostringstream ss;
                if (num1 == 0)
                    _err_DivideZero();
                ss << (num2 / num1);
                num = ss.str();
                cal.push(num);
                num.clear();
                c.pop();
            }
            else if ( c.front() == '^' )
            {
                std::ostringstream ss;
                ss << pow( num2, num1 );
                num = ss.str();
                cal.push(num);
                num.clear();
                c.pop();
            }
        }
    }
    num = cal.top();
    cal.pop();
    return std::stod(num);
}

void CalExpression( std::string _str )
{
    //去除输入的表达式内的所有空格和制表符
    const char* _character = _str.c_str();
    char character[ strlen(_character) ];
    int j=0;
    for ( int i=0; _character[i]!='\000'; i++ )
    {
        if ( _character[i]!=' ' && _character[i]!='\t' )
        {
            character[j] = _character[i];
            j++;
        }
    }
    character[j] = '\000';
    if ( character[2] == '\000') //合法的表达式至少要有三个字符
        _err_exp();
    const char* character_const = character;
    std::queue q = Infix2Postfix( character_const );
    double result = CalPostfix( q );
    for(int i=0; i<strlen(character); i++)
        std::cout << character[i];
    std::cout << " = " << result << std::endl;
}